#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *p = head, *q = p->next, *t = nullptr;
        head = q;
        while (1)
        {
            p->next = q->next;
            q->next = p;
            if (t != nullptr)
                t->next = q;
            if (p->next == nullptr || p->next->next == nullptr)
                return head;
            t = p;
            p = p->next;
            q = p->next;
        }
        return head;
    }

    // 可以设置一个虚拟头节点
    ListNode* swapPairsHaveDummyHead(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }

private:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
};

int main()
{
    // TODO
    return 0;
}
